#include "tbp_build.h"
#include "utils.h"
#include <cstring>
#include <iostream>
#include <queue>

namespace tbp {
std::vector<uint32_t> order;

void TBP_Build(BiGraph &graph, Indexes &idx) {
  std::cout << "start build\n";
  Timer timer;
  timer.start();
  /** 1. get order
   *  2. build lable_in and lable_out
   *  3. traversal vertices by order
   */

  auto order_vec = graph.vertex_order_; // global var
  order.resize(order_vec.size() + 1);
  for (int i = 0; i < order_vec.size(); i++) {
    order[order_vec[i]] = i;
  }
  idx.resize(graph.upper_size_);
  // traversal vertices
  for (auto vertex_id : graph.vertex_order_) {
    std::cout << "id == " << vertex_id << "\n";
    Indexes tmp(graph.upper_size_);
    // std::vector<time_pair>& edge_time = graph.upper_edge_time_[vertex_id];
    std::set<uint32_t> &start_time_set = graph.upper_edge_time_set_[vertex_id];
    std::set<uint32_t> &start_time_set_end =
        graph.upper_edge_time_set_end_[vertex_id];
    // traversal different start time
    // Label in
    for (auto time : start_time_set) {
      // std::cout << "time in = " << time << "\n";
      MOReach_in(graph, vertex_id, time, tmp.label_in_);
    }
    FindCanonical(tmp, idx);
    Insert2Lable(idx, tmp); // 插入到idx中
    tmp.handle_in = false;
    // Label out
    for (auto time : start_time_set_end) {
      // std::cout << "time out ===== " << time << "\n";
      MOReach_out(graph, vertex_id, time, tmp.label_out_);
    }
    FindCanonical(tmp, idx);
    Insert2Lable(idx, tmp);
  }

  timer.end();
  std::cout << "end, time = " << timer.GetTimeConsuming() << "\n";
}

void MOReach_in(BiGraph &graph, uint32_t u, uint32_t start_time,
                std::vector<std::vector<Entry>> &label_in) {

  // we need a Queue, array minT, array maxMinT
  // run algo1 line 1 to 3
  std::queue<queue_elem> que;
  std::vector<uint32_t> minT(graph.upper_size_ + 1,
                             std::numeric_limits<std::uint32_t>::max());
  std::vector<uint32_t> maxMinT(graph.lower_size_ + 1,
                                std::numeric_limits<std::uint32_t>::max());
  minT[u] = 0;
  que.push(queue_elem(u, start_time));

  bool *visited = new bool[graph.edge_size_];
  std::memset(visited, false, graph.edge_size_ * sizeof(bool));

  // uint32_t *edges = graph.Get_U_Edges(u);
  time_pair *edge_time = graph.Get_U_Edge_Time(u);
  uint32_t degree = graph.Get_U_Degree(u);
  for (uint32_t i = 0; i < degree; i++) {
    if (edge_time[i].first != start_time) {
      visited[graph.Get_UEdge_Idx(u) + i] = true;
    }
  }

  while (!que.empty()) {
    // std::cout << que.size() << "\n";
    auto elem = que.front();
    que.pop();
    uint32_t elem_id = elem.first;
    uint32_t te = elem.second;
    if (elem_id != u) {
      // build entry
      Entry candi(u, start_time, te);
      // check dominate
      // paper P1, 标签中节点的全局序列一定小于当前节点的序列
      if (order[u] < order[elem_id]) {
        std::vector<Entry> &vec = label_in[elem_id];
        InsertDominate(candi, vec);
      }
    }

    // run algo1 line 11 to 19
    uint32_t *edges = graph.Get_U_Edges(elem_id);
    time_pair *edge_time = graph.Get_U_Edge_Time(elem_id);
    uint32_t degree = graph.Get_U_Degree(elem_id);
    uint32_t edge_start_idx = graph.Get_UEdge_Idx(elem_id);
    // 遍历elem_id节点的所有边
    for (int i = 0; i < degree; i++) {
      uint32_t v = edges[i];
      uint32_t t1 = edge_time[i].first;
      uint32_t t2 = edge_time[i].second;
      if (visited[i + edge_start_idx])
        continue;
      if (t1 < te)
        continue;

      visited[i + edge_start_idx] = true;
      uint32_t t = 0;
      if (t1 >= maxMinT[v])
        continue;

      // 遍历v的邻居
      uint32_t *v_edges = graph.Get_L_Edges(v);
      time_pair *v_edge_time = graph.Get_L_Edge_Time(v);
      uint32_t v_degree = graph.Get_L_Degree(v);
      for (int j = 0; j < v_degree; j++) {
        uint32_t w_p = v_edges[j];
        // 替换的算法第14行，但是逻辑上感觉不对
        if (order[w_p] <= order[u])
          continue;
        // 找到所有和wp相连边

        uint32_t t1_p = v_edge_time[j].first;
        uint32_t t2_p = v_edge_time[j].second;
        if (t2_p >= minT[w_p])
          continue;
        if (std::min(t2, t2_p) > std::max(t1, t1_p)) {
          // if overlapping
          que.push(queue_elem(w_p, t2_p));
          minT[w_p] = t2_p;
        }

        if (minT[w_p] > t) {
          t = minT[w_p];
        }
      }
      maxMinT[v] = t;
    }
  }
  delete[] visited;
}

void MOReach_out(BiGraph &graph, uint32_t u, uint32_t end_time,
                 std::vector<std::vector<Entry>> &label_out) {
  std::queue<queue_elem>
      que; // 在endtime时间到达u，最晚出发时间(id,最晚出发时间)
  std::vector<uint32_t> maxT(graph.upper_size_ + 1, 0);
  std::vector<uint32_t> minMaxT(graph.lower_size_ + 1, 0);
  maxT[u] = std::numeric_limits<uint32_t>::max();
  que.push(queue_elem(u, end_time));
  // same as MOReach_in
  bool *visited = new bool[graph.edge_size_];
  std::memset(visited, false, graph.edge_size_ * sizeof(bool));

  // uint32_t *edges = graph.Get_U_Edges(u);
  time_pair *edge_time = graph.Get_U_Edge_Time(u);
  uint32_t degree = graph.Get_U_Degree(u);
  for (uint32_t i = 0; i < degree; i++) {
    if (edge_time[i].second != end_time) {
      visited[graph.Get_UEdge_Idx(u) + i] = true;
    }
  }

  while (!que.empty()) {
    auto elem = que.front();
    que.pop();
    uint32_t elem_id = elem.first;
    uint32_t ts = elem.second;
    if (elem_id != u) {
      // build entry
      Entry candi(u, ts, end_time);
      // paper P1, 标签中节点的全局序列一定小于当前节点的序列
      if (order[u] < order[elem_id]) {
        // std::cout << u << " " << candi << "\n";
        auto &vec = label_out[elem_id];
        InsertDominate(candi, vec);
      }
    }

    // run algo1 line 11 to 19
    uint32_t *edges = graph.Get_U_Edges(elem_id);
    time_pair *edge_time = graph.Get_U_Edge_Time(elem_id);
    uint32_t degree = graph.Get_U_Degree(elem_id);
    uint32_t edge_start_idx = graph.Get_UEdge_Idx(elem_id);

    for (int i = 0; i < degree; i++) {
      uint32_t v = edges[i];
      uint32_t t1 = edge_time[i].first;
      uint32_t t2 = edge_time[i].second;
      if (visited[i + edge_start_idx])
        continue;

      if (t2 > ts)
        continue;

      visited[i + edge_start_idx] = true;
      uint32_t t = 0;
      if (t2 <= minMaxT[v])
        continue;
      uint32_t *v_edges = graph.Get_L_Edges(v);
      time_pair *v_edge_time = graph.Get_L_Edge_Time(v);
      uint32_t v_degree = graph.Get_L_Degree(v);

      for (int j = 0; j < v_degree; j++) {
        uint32_t w_p = v_edges[j];

        if (order[w_p] <= order[u])
          continue;
        uint32_t t1_p = v_edge_time[j].first;
        uint32_t t2_p = v_edge_time[j].second;
        if (t1_p <= maxT[w_p])
          continue;
        if (std::min(t2, t2_p) > std::max(t1, t1_p)) {
          // if overlapping
          que.push(queue_elem(w_p, t1_p));
          maxT[w_p] = t1_p;
        }

        if (maxT[w_p] < t) {
          t = maxT[w_p];
        }
      }
      minMaxT[v] = t;
    }
  }
}

void InsertDominate(Entry &candi, std::vector<Entry> &vec) {
  if (vec.empty()) {
    vec.push_back(candi);
    return;
  }

  // for (auto t : vec) {
  //   if (t.id_ == candi.id_ && candi.start_ <= t.start_ && candi.end_ >=
  //   t.end_)
  //     return;
  // }

  auto it = vec.begin();
  while (it != vec.end()) {
    Entry e = *it;
    if (e.id_ != candi.id_) {
      it++;
    } else {
      if (candi.start_ >= e.start_ && candi.end_ <= e.end_) {
        it = vec.erase(it);
      } else {
        it++;
      }
    }
  }
  vec.push_back(candi);
}

/**
 * 看能不能从已知信息推出候选索引项
 */
void FindCanonical(Indexes &candidate, const Indexes &res) {
  // 根据论文的意思，好像labelin和labelout是分开计算的

  if (candidate.handle_in) {
    // 处理 in
    std::vector<std::vector<Entry>> &vec = candidate.label_in_;
    // 遍历每一个entry
    for (int i = 1; i < vec.size(); i++) {
      std::vector<Entry> &l_in = vec[i];
      auto it = l_in.begin();
      while (it != l_in.end()) {
        Entry e = *it;
        // std::cout << e << "\n";
        if (Query(e.id_, i, time_pair(e.start_, e.end_), res)) {
          // 可以由已知条件推出
          it = l_in.erase(it);
        } else {
          it++;
        }
      }
    }

  } else if (candidate.label_in_.empty()) {
    // 处理out
    std::vector<std::vector<Entry>> &vec = candidate.label_out_;
    for (int i = 1; i < vec.size(); i++) {
      std::vector<Entry> &l_out = vec[i];
      auto it = l_out.begin();
      while (it != l_out.end()) {
        Entry e = *it;
        if (Query(i, e.id_, time_pair(e.start_, e.end_), res)) {
          it = l_out.erase(it);
        } else {
          it++;
        }
      }
    }
  }
}
bool Query(uint32_t u, uint32_t w, time_pair time_interval,
           const Indexes &origin) {
  uint32_t Is = time_interval.first;
  uint32_t Ie = time_interval.second;
  auto Label_out_u = origin.label_out_[u];
  auto label_in_w = origin.label_in_[w];
  int i = 0, j = 0;
  // std::cout << Label_out_u.size() << "====" << label_in_w.size() << "\n";
  while (i < Label_out_u.size() && j < label_in_w.size()) {
    Entry e = Label_out_u[i];
    Entry e_p = label_in_w[j];
    if (e.id_ == w && e.start_ >= Is && e.end_ <= Ie)
      return true;
    else if (e_p.id_ == u && e_p.start_ >= Is && e_p.end_ <= Ie)
      return true;
    else if (e.id_ == e_p.id_) {
      if (e.start_ >= Is && e.end_ <= Ie && e_p.start_ >= e.end_ &&
          e_p.end_ <= Ie) {
        return true;
      }else{
        i++;j++;
      }
    } else if (order[e.id_] < order[e_p.id_])
      i++;
    else if (order[e.id_] < order[e_p.id_])
      j++;
    else {
      i++;
      j++;
    }
  }
  return false;
}

void Insert2Lable(Indexes &res, Indexes &candidate) {
  // 插入之后要对res中每个entry进行排序
  if (candidate.handle_in) {
    auto &vec = candidate.label_in_;
    for (int i = 1; i < vec.size(); i++) {
      for (auto t : vec[i]) {
        res.label_in_[i].push_back(t);
      }
    }
    // 重新排序
    for (int i = 1; i < res.label_in_.size(); i++) {
      std::sort(res.label_in_[i].begin(), res.label_in_[i].end(),
                [](Entry &first, Entry &second) {
                  if (order[first.id_] == order[second.id_]) {
                    // 论文中要求先按照order排序，随后按照ending time升序
                    return first.end_ < second.end_;
                  }
                  return order[first.id_] < order[second.id_];
                });
    }
  } else {
    auto &vec = candidate.label_out_;
    for (int i = 1; i < vec.size(); i++) {
      for (auto t : vec[i]) {
        res.label_out_[i].push_back(t);
      }
    }
    // 重新排序
    for (int i = 1; i < res.label_out_.size(); i++) {
      std::sort(res.label_out_[i].begin(), res.label_out_[i].end(),
                [](Entry &first, Entry &second) {
                  if (order[first.id_] == order[second.id_]) {
                    // 论文中要求先按照order排序，随后按照ending time升序
                    return first.end_ < second.end_;
                  }
                  return order[first.id_] < order[second.id_];
                });
    }
  }
}

} // namespace tbp
